package LeetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class LC_336_PalindromePairs {

    public static void main(String[] args) {

    }

    class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> result = new ArrayList<>();
            HashMap<String, Integer> map = new HashMap<>();
            for (int i = 0; i < words.length; i++)
                map.put(words[i], i);
            for (int i = 0; i < words.length; i++) {
                String s = words[i];
                if (isPalindrome(s)) {
                    if (map.containsKey("")) {
                        if (map.get("") != i) {
                            ArrayList<Integer> l = new ArrayList<>();
                            l.add(i);
                            l.add(map.get(""));
                            result.add(l);

                            l = new ArrayList<>();

                            l.add(map.get(""));
                            l.add(i);
                            result.add(l);
                        }

                    }
                }

                String reversed = new StringBuilder(s).reverse().toString();
                if (map.containsKey(reversed)) {
                    if (map.get(reversed) != i) {
                        ArrayList<Integer> l = new ArrayList<>();
                        l.add(i);
                        l.add(map.get(reversed));
                        result.add(l);
                    }
                }

                for (int k = 1; k < s.length(); k++) {
                    String left = s.substring(0, k);
                    String right = s.substring(k);

                    if (isPalindrome(left)) {
                        String reversedRight = new StringBuilder(right).reverse().toString();
                        if (map.containsKey(reversedRight)) {
                            if (map.get(reversedRight) != i) {
                                ArrayList<Integer> l = new ArrayList<>();
                                l.add(map.get(reversedRight));
                                l.add(i);
                                result.add(l);
                            }
                        }
                    }

                    if (isPalindrome(right)) {
                        String reversedLeft = new StringBuilder(left).reverse().toString();
                        if (map.containsKey(reversedLeft)) {
                            if (map.get(reversedLeft) != i) {
                                ArrayList<Integer> l = new ArrayList<>();
                                l.add(i);
                                l.add(map.get(reversedLeft));
                                result.add(l);
                            }
                        }
                    }

                }
            }
            return result;
        }

        boolean isPalindrome(String s) {
            int i = 0;
            int j = s.length() - 1;
            while (i < j) {
                if (s.charAt(i) != s.charAt(j)) return false;
                i++;
                j--;
            }
            return true;
        }

    }
}